import kotlin.system.measureTimeMillis

fun <T,R> ((T)->R).memorize():((T)->R){
    val original =  this
    val cache = mutableMapOf<T,R>()
    return { n:T -> cache.getOrPut(n) {original(n)}}
}

lateinit var fib: (Int) ->Long
fib = {
    n:Int->
        when(n){
            1,0 -> 1L
            else -> fib(n-1) + fib(n-2)
        }
}.memorize()

println(fib(100))
println(fib(500))
println(measureTimeMillis { fib(40) } )
println(measureTimeMillis { fib(500) })
println(measureTimeMillis { fib(2000) })
println(measureTimeMillis { fib(4000) })
println(measureTimeMillis { fib(5000) })